/**
 * @file
 * Provide storage for instances of extension graph 
 */

#ifndef EXPANSION_GRAPH_INSTANCE_H
#define EXPANSION_GRAPH_INSTANCE_H

#include <iostream>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <sstream>


#include "expansion_graph.h"

/**
 * @brief Provide storage for instances of extension graph.
 */
template<class V, class E>
class ExpansionGraphInstance
{
 public:
  ExpansionGraphInstance(ExpansionGraph<V, E> *given);
  ExpansionGraphInstance(ExpansionGraphInstance &given);

  void add_vertex(V *v);
  void add_edge(E *e);
  void set_parent(ExpansionGraphInstance<V, E> *parent);

  void get_vertices(std::set<V* > **result);
  void get_edges(std::set<E* > **result);
  void get_graph(ExpansionGraph<V, E> **result);
  void copy_edges(std::set<E* > *result);

  bool get_constrained_expansions(V *v, std::map<E*, V*> *result); 
  void get_parent(ExpansionGraphInstance<V, E> **result);
  bool check_adjacency(E *e, V *v1, V *v2);
  bool has_edge(E *e);
  void expand(std::list<ExpansionGraphInstance<V, E> *> *result);
  void unique_expand(std::map<std::set< E*>, ExpansionGraphInstance<V,E>* > *occured, std::list<ExpansionGraphInstance<V, E> *> *result);

  std::string get_canonical_label();
  std::vector< E*> get_expansion_order();
  void add_expansion_order(std::vector<E *> given);
  void update_canonical_label(std::vector<E *> given);
  
 private:
  ExpansionGraph<V, E> *graph;
  std::set<V *> vertices;
  std::set<E *> edges;

  std::vector<E *> expansion;
  std::set<std::vector<E* > > expansion_set;

  bool has_parent;
  ExpansionGraphInstance<V, E> *parent_;

  int *canonical_label;
  bool computed;
};

template<class V, class E>
  std::vector< E*> ExpansionGraphInstance<V,E>::get_expansion_order()
{
  return expansion;
}

template<class V, class E>
  void ExpansionGraphInstance<V,E>::add_expansion_order(std::vector<E *> given)
{
  expansion_set.insert(given);
}


/**
 * Construct a instance with reference to a graph.
 * @param[in] given The reference graph. 
 */
template<class V, class E>
  ExpansionGraphInstance<V,E>::ExpansionGraphInstance(ExpansionGraph<V, E> *given) 
{
  graph = given;
  computed = false;
}

/**
 * Insert a vertex.
 * @param[in] v The vertex to be inserted.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::add_vertex(V *v) 
{
  vertices.insert(v);
}

/**
 * Insert an edge.
 * @param[in] e The edge to be added.
 */
template<class V, class E>
void ExpansionGraphInstance<V,E>::add_edge(E *e) 
{
  if(edges.find(e) == edges.end())
    {
      edges.insert(e);
      expansion.push_back(e);
    }
}

/**
 * Get vertices in the instance.
 * @param[out] result The result location to write to.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::get_vertices(std::set<V* > **result) 
{ 
  *result = &vertices;
}

/**
 * Get edges in the instance.
 * @param[out] result The result location to write to.
 */
template<class V, class E>
void ExpansionGraphInstance<V,E>::get_edges(std::set<E* > **result) 
{ 
  *result = &edges;
}

/**
 * Get expansions of a vertex.
 * @param[in] v The vertex whose expansions are requested.
 * @param[out] result The result location to write to.
 * @return @c true if the vertex is present, @c false otherwise.
 */
template<class V, class E>
bool ExpansionGraphInstance<V,E>::get_constrained_expansions(V *v, 
                                                             std::map<E*, V*> *result) 
{ 
  return graph->get_expansions_subset(v, &edges, result);
}

/**
 * Check if two vertices are connected by a given edge. 
 * Note that there are two parts to this check, first is there an edge 
 * between the given vertices and second does this edge have the given 
 * 'value'.
 * @param[in] e The given edge, whose value is relevant, not the instance.
 * @param[in] v1 The first vertex, the particular instance is relevant.
 * @param[in] v2 The other vertex, the particular instance is relevant.
 * @return @c true if check successfull, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraphInstance<V,E>::check_adjacency(E *e, 
                                                    V *v1,
                                                    V *v2)
{
  // Try to get the constrained expansions for the first vertex
  std::map<E*, V*> expansions1;
  if(get_constrained_expansions(v1, &expansions1))
    {
      // Iterate over the expansions
      for(typename std::map<E*, V*>::iterator i = expansions1.begin();
          i != expansions1.end();
          i++)
        if ((*(i->first) == *e) // Check for the correct edge 'value' 
            && ((i->second) == v2)) // Check for the presence of an edge
          return true;
      
      // There is no edge or there is no edge with the given 'value'
      return false;
    }
  // There were no constrained expantions to be found
  else
    return false; 
}

/**
 * Sets the parent instance of this instance.
 * @param[in] parent The parent instance of this instance.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::set_parent(ExpansionGraphInstance<V, E> *parent)
{
  has_parent = true;
  parent_ = parent;
}

/**
 * Gets the parent graph of this instance.
 * @param[out] result The parent graph of this instance.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::get_graph(ExpansionGraph<V, E> **result)
{
  *result = graph;
}

/**
 * Gets the parent instance of the instance.
 * @param[out] result The parent instance of the instance.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::get_parent(ExpansionGraphInstance<V,E> **result)
{
  *result = parent_;
}

/**
 * Copy constructor.
 * @param[in] Instance from which to construct from.
 */
template<class V, class E>
  ExpansionGraphInstance<V,E>::ExpansionGraphInstance(ExpansionGraphInstance &given)
{
  graph = given.graph;
  vertices = given.vertices;
  edges = given.edges;

  expansion = given.expansion;
  computed = false;

  if(given.has_parent)
    {
    has_parent = true;
    parent_ = given.parent_;  
    }
}

/**
 * Check if a given edge is present in the instance.
 * @param[in] The given edge.
 * @return @c true if the edge is present @c false otherwise. 
 */
template<class V, class E>
  bool ExpansionGraphInstance<V,E>::has_edge(E *e)
{
  return edges.find(e) != edges.end();
}

/**
 * Expand instance.
 * @param[in] result The list of expanded instances.
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::expand(std::list<ExpansionGraphInstance<V, E> *> *result)
{
  ExpansionGraph<V, E> *curr_graph;
  this->get_graph(&curr_graph);

  for(typename std::set<V *>::iterator i = vertices.begin();
      i != vertices.end();
      i++)
    {      
      std::map<E*, V*> curr_vertex_expansions;
      curr_graph->get_expansions(*i, &curr_vertex_expansions);
      
      for(typename std::map<E*, V*>::iterator j = curr_vertex_expansions.begin();
          j != curr_vertex_expansions.end();
          j++)
        {
          if(! this->has_edge(j->first))
            {
              ExpansionGraphInstance<V, E> *curr_instance = new ExpansionGraphInstance<V, E>(*this);
              curr_instance->add_edge(j->first);
              curr_instance->add_vertex(j->second);
              curr_instance->set_parent(this);
              result->push_back(curr_instance);
            }
        }
    }
}

/**
 * 
 */
template<class V, class E>
  void ExpansionGraphInstance<V,E>::copy_edges(std::set<E* > *result)
{
  *result = this->edges;
}

template<class V, class E>
  void ExpansionGraphInstance<V,E>::unique_expand(std::map<std::set< E*>, ExpansionGraphInstance<V,E> * > *occured, 
                                                  std::list<ExpansionGraphInstance<V, E> *> *result)
{
  ExpansionGraph<V, E> *curr_graph;
  this->get_graph(&curr_graph);

  for(typename std::set<V *>::iterator i = vertices.begin();
      i != vertices.end();
      i++)
    {      
      std::map<E*, V*> curr_vertex_expansions;
      curr_graph->get_expansions(*i, &curr_vertex_expansions);
      
      for(typename std::map<E*, V*>::iterator j = curr_vertex_expansions.begin();
          j != curr_vertex_expansions.end();
          j++)
        {
          if(! this->has_edge(j->first))
            {
              std::set< E*> *curr_edges = new std::set< E*>;
              this->copy_edges(curr_edges);
              curr_edges->insert(j->first);


              ExpansionGraphInstance<V, E> *curr_instance = new ExpansionGraphInstance<V, E>(*this);
              curr_instance->add_edge(j->first);
              curr_instance->add_vertex(j->second);
              curr_instance->set_parent(this);

              if (occured->find(*curr_edges) == occured->end())
                {
                  curr_instance->update_canonical_label(curr_instance->get_expansion_order());
                  occured->insert(std::pair<std::set< E*>, ExpansionGraphInstance<V, E> * >(*curr_edges, curr_instance));
                  result->push_back(curr_instance);
                }
              else
                {
                  ((occured->find(*curr_edges))->second)->update_canonical_label(curr_instance->get_expansion_order());
                  delete curr_instance;
                }
              delete curr_edges;
            }
        }
    }
}

/**
 * 
 */
template <class V, class E>
  std::string ExpansionGraphInstance<V, E>::get_canonical_label()
{
  std::string canonical_label_string = "";
  
  for(int p = 0; p < edges.size() * 3; p++)
    {
      std::ostringstream oss;
      oss << canonical_label[p];
      canonical_label_string.append(oss.str());
    }
      
  delete[] canonical_label;
  
  return canonical_label_string;
}

template <class V, class E>
void ExpansionGraphInstance<V, E>::update_canonical_label(std::vector<E *> given)
{
  if (! computed)
    {
      computed = true;
      canonical_label = new int[edges.size() * 3];

      int position = 0;
      
      for(typename std::vector<E* >::iterator i  = given.begin();
          i != given.end();
          i++)
        {
          canonical_label[position] = (*i)->get_int_value();
          position++;
          
          int vertex1 = (graph->get_edge1(*i))->get_int_value();
          int vertex2 = (graph->get_edge2(*i))->get_int_value();
          
          if (vertex1 > vertex2)
            {
              int temp;
              temp = vertex1;
              vertex1 = vertex2;
              vertex2 = temp;
            }
                  
          canonical_label[position] = vertex1;
          position++;
          canonical_label[position] = vertex2;
          position++;
        }

/*       std::cout << "Canonical Label Initialized: "; */
/*       for(int k = 0; k < edges.size() * 3; k++) */
/*         std::cout << canonical_label[k] << " "; */
/*       std::cout << "\n"; */

    }
  else
    {
      int *new_canonical_label = new int[edges.size() * 3];

      int position = 0;
      
      for(typename std::vector<E* >::iterator i  = given.begin();
          i != given.end();
          i++)
        {
          new_canonical_label[position] = (*i)->get_int_value();
          position++;
          
          int vertex1 = (graph->get_edge1(*i))->get_int_value();
          int vertex2 = (graph->get_edge2(*i))->get_int_value();
          
          if (vertex1 > vertex2)
            {
              int temp;
              temp = vertex1;
              vertex1 = vertex2;
              vertex2 = temp;
            }
                  
          new_canonical_label[position] = vertex1;
          position++;
          new_canonical_label[position] = vertex2;
          position++;
        }
    
/*       std::cout << "Previous Canonical Label: "; */
/*       for(int k = 0; k < edges.size() * 3; k++) */
/*         std::cout << canonical_label[k] << " "; */
/*       std::cout << "\n"; */

      bool replace = false;
      for(int p = 0; p < edges.size() * 3 ; p++)
        if ( canonical_label[p] != new_canonical_label[p] )
          {
            if (canonical_label[p] < new_canonical_label[p])
              replace = true;        
            break;
          }
          
      if(replace)
        for(int p = 0; p < edges.size() * 3; p++)
          canonical_label[p] = new_canonical_label[p];


/*   std::cout << "New Canonical Label: "; */
/*   for(int k = 0; k < edges.size() * 3; k++) */
/*     std::cout << new_canonical_label[k] << " "; */
/*   std::cout << "\n"; */
/*   std::cout << "Selected Canonical Label: "; */
/*   for(int k = 0; k < edges.size() * 3; k++) */
/*     std::cout << canonical_label[k] << " "; */
/*   std::cout << "\n"; */
/*   std::cout << "\n"; */

      delete[] new_canonical_label;
    }


}

#endif // EXPANSION_GRAPH_INSTANCE_H

